package q538_convertBST;

import CommonClass.Common.TreeNode;
public class Solution_2 {
    int prev = 0;
    /*
    用回溯的方法解决 同样是更改中序遍历为 右 中 左 即可
    同时用一个数记录上一个节点值
     */
    public TreeNode convertBST(TreeNode root) {
        dfs(root);
        return root;
    }

    private void dfs(TreeNode root) {
        if (root == null){
            return;
        }
        // 右
        dfs(root.right);
        // 根
        root.val += prev;
        prev = root.val;
        // 左
        dfs(root.left);
    }

}
